package com.code.test.dance;

import com.code.test.first.link.ListNode;

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * https://leetcode.cn/problems/7WHec2/description/
 * <p>
 * LCR 077. 排序链表
 * <p>
 * 给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 *
 * 输入：head = [4,2,1,3]
 * 输出：[1,2,3,4]
 */
public class SortLink {

    public static void main(String[] args) {
        int[] nums = {4, 2, 1, 3};
        LinkNode node = build(nums);
        LinkNode ret = sortList(node);

        while (ret != null) {
            System.out.println(ret.val);
            ret = ret.next;
        }
    }

    public static LinkNode build(int[] nums) {
        LinkNode ret = new LinkNode(nums[0]);
        LinkNode cur = ret;
        for (int i = 1; i < nums.length; i++) {
            LinkNode node = new LinkNode(nums[i]);
            cur.next = node;
            cur = node;
        }
        return ret;
    }

    public static LinkNode sortWithQueue(LinkNode head) {
        PriorityQueue<LinkNode> queue = new PriorityQueue<>(new Comparator<LinkNode>() {
            @Override
            public int compare(LinkNode l1, LinkNode t1l2) {
                return l1.val - t1l2.val;
            }
        });

        while (head != null) {
            queue.offer(head);
            head = head.next;
        }

        LinkNode dummy = new LinkNode(0);

        LinkNode cur = dummy;

        // 挨个取出来，放到新的节点上
        while (queue.size() > 0) {
            cur.next = queue.peek();
            queue.poll();
            cur = cur.next;
        }
        cur.next = null;
        return dummy.next;

    }

    /**
     * 通过快慢指针 ，把链表分成2个，然后再合并
     */
    public static LinkNode sortList(LinkNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        LinkNode dummy = new LinkNode(-1);
        dummy.next = head;
        LinkNode fast = dummy, slow = dummy;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = slow.next;
        slow.next = null;
        return merge(sortList(head), sortList(fast));
    }

    public static LinkNode merge(LinkNode l1, LinkNode l2) {
        LinkNode dummy = new LinkNode(0);
        LinkNode p1 = l1;
        LinkNode p2 = l2;
        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                dummy.next = p1;
                p1 = p1.next;
            } else {
                dummy.next = p2;
                p2 = p2.next;
            }
        }
        if (p1 != null) {
            dummy.next = p1;
        }
        if (p2 != null) {
            dummy.next = p2;
        }

        return dummy.next;
    }
}
